package Leetcode.网格图;

import java.util.*;

/**
 * @Author: kirito
 * @Date: 2024/5/4 12:26
 * @Description:
 * 腐烂的橘子
 * 已解答
 * 中等
 * 相关标签
 * 相关企业
 * 在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
 *
 * 值 0 代表空单元格；
 * 值 1 代表新鲜橘子；
 * 值 2 代表腐烂的橘子。
 * 每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
 *
 * 返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
 * 输出：4
 * 示例 2：
 *
 * 输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
 * 输出：-1
 * 解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个方向上。
 * 示例 3：
 *
 * 输入：grid = [[0,2]]
 * 输出：0
 * 解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。
 *
 *
 * 提示：
 *
 * m == grid.length
 * n == grid[i].length
 * 1 <= m, n <= 10
 * grid[i][j] 仅为 0、1 或 2
 */

public class orangesRotting {
    // 定义方向数组，用于在网格中上下左右移动
    int[] dr = new int[]{-1, 0, 1, 0};
    int[] dc = new int[]{0, -1, 0, 1};

    public int orangesRotting(int[][] grid) {
        // 获取网格的行数和列数
        int R = grid.length, C = grid[0].length;
        // 使用双端队列存储网格中的位置及其腐败程度
        Queue<Integer> queue = new ArrayDeque<Integer>();
        // 使用哈希表存储每个位置的腐败程度
        Map<Integer, Integer> depth = new HashMap<Integer, Integer>();
        // 遍历网格，将所有腐败的橙子及其腐败程度加入队列
        for (int r = 0; r < R; ++r) {
            for (int c = 0; c < C; ++c) {
                if (grid[r][c] == 2) {
                    int code = r * C + c;
                    queue.add(code);
                    depth.put(code, 0);
                }
            }
        }
        int ans = 0;
        // 当队列不为空时，进行广度优先搜索
        while (!queue.isEmpty()) {
            // 取出队列的第一个元素
            int code = queue.remove();
            // 计算该元素在网格中的行和列
            int r = code / C, c = code % C;
            // 遍历所有可能的移动方向
            for (int k = 0; k < 4; ++k) {
                // 计算移动后的行和列
                int nr = r + dr[k];
                int nc = c + dc[k];
                // 如果新的位置在网格范围内，并且是新鲜的橙子
                if (0 <= nr && nr < R && 0 <= nc && nc < C && grid[nr][nc] == 1) {
                    // 将新鲜的橙子变为腐败的，并记录其腐败程度
                    grid[nr][nc] = 2;
                    int ncode = nr * C + nc;
                    queue.add(ncode);
                    depth.put(ncode, depth.get(code) + 1);
                    // 更新最短的腐败程度
                    ans = Math.max(ans, depth.get(ncode));
                }
            }
        }
        // 遍历网格，如果还有新鲜的橙子，返回-1
        for (int[] row: grid) {
            for (int v: row) {
                if (v == 1) {
                    return -1;
                }
            }
        }
        // 如果所有橙子都变质了，返回最短腐败程度
        return ans;
    }

    /**
     * 这个思路好理解很多
     * 记录新鲜橘子个数，和已经腐烂的句子位置，用队列保存
     *
     * 然后遍历腐烂橘子，记录每分钟的次数，如果没有新鲜句子就返回时间
     *
     * @param grid
     * @return
     */
    public int orangesRotting2(int[][] grid) {
        // 统计新鲜橙子
        int freshNum = 0;
        // dfs 统计腐烂橙子
        Deque<int[]> queue = new ArrayDeque<>();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 1) {
                    freshNum++;
                }
                if (grid[i][j] == 2) {
                    queue.offer(new int[]{i, j});
                }
            }
        }
        int minutes = 0;
        //如果没有新橘子被感染了，那么队列就会为空，就要么没有新鲜橘子被感染了，要么就感染不到了
        while (!queue.isEmpty()) {
            if (freshNum == 0) {
                // 没有新鲜橙子了
                return minutes;
            }
            // 过去1分钟，周围开始腐烂
            minutes++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] rot = queue.pop();
                int x = rot[0];
                int y = rot[1];
                freshNum -= roting(grid, x - 1, y, queue);
                freshNum -= roting(grid, x + 1, y, queue);
                freshNum -= roting(grid, x, y - 1, queue);
                freshNum -= roting(grid, x, y + 1, queue);
            }
        }
        // 腐烂过程结束
        return freshNum > 0 ? -1 : minutes;
    }

    private int roting(int[][] grid, int x, int y, Deque<int[]> queue) {
        if (x < 0
        || y < 0
        || x > grid.length - 1
        || y > grid[0].length - 1
        || grid[x][y] != 1) {
            return 0;
        }
        // grid[x][y] = 1
        grid[x][y] = 2;
        //每感染一个新橘子就加入队列
        queue.offer(new int[]{x, y});
        return 1;
    }
}
